package leetcode.code1575;

import leetcode.IDebug;

public class Solution implements IDebug {

	int mod = (int) 1e9 + 7;

	public int countRoutes(int[] locations, int start, int finish, int fuel) {
		int n = locations.length;
		long[][] dp = new long[fuel + 1][n];
		for (int i = 0; i <= fuel; i++) {
			for (int from = 0; from < n; from++) {
				if (from == finish)
					dp[i][from] = 1;
				for (int to = 0; to < n; to++) {
					if (from != to && i - Math.abs(locations[from] - locations[to]) >= 0) {
						dp[i][from] += dp[i - Math.abs(locations[from] - locations[to])][to];
					}
					dp[i][from] %= mod;
				}
			}
		}
		return (int) dp[fuel][start];
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
